package _02_并查集;
/*
    基于rank的优化，将矮的树嫁接到高的树
 */
public class QuickUnion_Rank extends QuickUnion{
    private int[] ranks; //存放每棵树的高度
    public QuickUnion_Rank(int capacity) {
        super(capacity);
        ranks = new int[capacity];
        for (int i = 0; i < ranks.length; i++) {
            ranks[i] = 1; //初始化时，每棵树的节点都为1
        }
    }

    /*
        将v1的根节点嫁接到v2的根节点上
     */
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1); //v1的根节点
        int p2 = find(v2); // v2的根节点

        if(p1 == p2) return;

        if(ranks[p1]< ranks[p2]){ //p1的高度小于p2的高度
            parents[p1] = p2; //将p1嫁接到p2上
        }else if(ranks[p1] > ranks[p2]){
            parents[p2] = p1;
        }else{
            parents[p1] = p2;
            ranks[p2]++;
        }
    }
}
